#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

class Solution {
public:
    int sort(vector<int> &vec, int i, int j)
    {
        int val = vec[i];
        while(i < j){
            while(i < j && vec[j] >= val)
                j--;
            if(i < j)
                vec[i++] = vec[j];
            while(i < j && vec[i] <= val)
                i++;
            if(i < j)
                vec[j--] = vec[i];
        }

        vec[i] = val;
        return i;
    }

    int getK(vector<int> &vec, int i, int j, int k, int len)
    {
        int pos = sort(vec, i, j);
        if(len - pos == k){
            return vec[pos];
        }else if(len - pos > k){
            return getK(vec, pos + 1, j, k, len);
        }else {
            return getK(vec, i, pos - 1, k, len);
        }
    }

    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        vector<int> vec(nums1);
        for(auto i: nums2){
            vec.push_back(i);
        }

        if(vec.size() == 1) return vec[0];

        int k = vec.size() / 2 + 1;
        int val1 = getK(vec, 0, vec.size() - 1, k, vec.size());
        if(vec.size() % 2 == 0){
            int val2 = getK(vec, 0, vec.size() - 1, k - 1, vec.size());
            return (float)(val1 + val2) / 2;
        }
        return val1;
    }
};

int main(int argc, char const *argv[])
{
    Solution sol;
    vector<int> vec1{1, 2, 3, 4, 5, 6};
    vector<int> vec2{5, 6, 7, 8, 9, 10};
    cout << sol.findMedianSortedArrays(vec1, vec2) << endl;
    return 0;
}
